package com.lzh.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author liuzhihao
 * @create 2021-10-21 0:32
 * 将中缀表达式转换为后缀表达式（逆波兰表达式）
 */
public class ChangeToPoland {
    public static void main(String[] args) {
        String expression = "1+((2+3)*4)-5";

        // 将expression 转换为List
        List<String> stringList = getStringList(expression);
        System.out.println(stringList);

        // 考虑多位数
        List<String> list = stringToList(expression);
        System.out.println(list);

        // 计算
        cal(list);
    }

    /**
     * 将中缀表达式转成逆波兰表达式，计算逆波兰表达式
     * @param list
     */
    public static void cal(List<String> list) {
        Stack<String> s1 = new Stack<>(); // 存放操作符
        List<String> s2 = new ArrayList<>(); // 存放操作数
        for (String listTemp : list) {
            if (listTemp.matches("\\d+")) { // 如果为数
                s2.add(listTemp);
            } else { // 如果不为数
                if (s1.empty()) { // 操作符栈为空
                    s1.push(listTemp);
                } else {
                    if ("(".equals(listTemp)) {
                        s1.push(listTemp);
                    } else if (")".equals(listTemp)) {
                        s2.add(s1.pop());
                        s1.pop();
                    } else {
                        if (compareOper(listTemp) > compareOper(s1.peek())) {
                            s2.add(listTemp);
                        } else {
                            s1.push(listTemp);
                        }
                    }
                }
            }
        }
        // 将s1中剩余压入s2
        while (!s1.empty()) {
            s2.add(s1.pop());
        }

        Stack<String> total = new Stack<>();
        int num1;
        int num2;
        int sum = 0;
        // 计算
        for (String item : s2) {
            if (item.matches("\\d+")) {
                total.push(item);
            } else {
                num1 = Integer.parseInt(total.pop());
                num2 = Integer.parseInt(total.pop());
                if ("+".equals(item)) {
                    sum = num1 + num2;
                    total.push(String.valueOf(sum));
                } else if ("-".equals(item)) {
                    sum = num2 - num1;
                    total.push(String.valueOf(sum));
                } else if ("*".equals(item)) {
                    sum = num2 * num1;
                    total.push(String.valueOf(sum));
                } else if ("/".equals(item)){
                    sum = num2 / num1;
                    total.push(String.valueOf(sum));
                }
            }
        }
        System.out.println("当前运算的结果为：:"+sum);
    }

    /**
     * 考虑多位数（整数）
     * @param s
     * @return
     */
    public static List<String> stringToList(String s) {
        List<String> list = new ArrayList<>();
        int index = 0;
        char c;
        String temp = "";
        do{

            if (isDigital(s.charAt(index))) { // 如果当前遍历到的数是数字
                temp += s.charAt(index);
                if (isDigital(s.charAt(index +1))) { // 如果当前遍历的数的下一个数也是数字
                    temp += s.charAt(index + 1);
                    index++;
                }
                list.add(temp);
                temp = "";
            } else {
                list.add(s.charAt(index)+"");
            }
            index++;

            if (index == s.length() - 1) {
                list.add(s.charAt(index)+"");
            }
        }while(index <= s.length() - 2);
        return list;
    }

    /**
     * 只考虑了一位数
     * @param s
     * @return
     */
    public static List<String> getStringList(String s) {
//        List<String> list = new ArrayList<>();
//        String[] split = s.split("");
//        for (String temp : split) {
//            list.add(temp);
//        }
//        return list;
        return new ArrayList<>(Arrays.asList(s.split(""))); // 一行代码
    }

    /**
     * 判断是否为数
     * @param c
     * @return
     */
    public static boolean isDigital(char c) {
        if (c == '+' || c =='-' || c == '*' || c == '/' || c == '(' || c == ')') {
            return false;
        }
        return true;
    }

    public static int compareOper(String s) {
        if (s == "+" || s == "-") {
            return 0;
        } else if (s == "*" || s == "/") {
            return 1;
        } else {
            return -1;
        }
    }

}



